package org.example.dataStructure.linkedList;

/**
 * @author yuwl
 * @description 链表实现 消息队列
 * 消息队列可以使用链表来实现，这样可以动态地添加和删除消息，并且没有固定的大小限制。下面是使用链表实现简单消息队列的基本思路：
 * 1.创建一个节点类，节点中包含消息内容和指向下一个节点的指针。
 * 2.创建一个消息队列类，该类中包含链表的头节点和尾节点，以及用于表示队列大小的变量。
 * 3.提供入队和出队操作的方法。入队操作在链表尾部添加新节点，出队操作从链表头部移除节点。
 *
 * 虽然以上方式实现的消息队列功能基本正确，但在实际使用中可能会遇到一些问题：
 * 1.线程安全性: 上述实现不是线程安全的。如果多个线程同时对队列进行操作，可能会导致竞态条件或数据不一致的问题。因此，在多线程环境下使用时，需要考虑添加适当的同步机制来确保线程安全。
 * 2.空间浪费: 每个消息都需要一个节点来存储，而节点除了存储消息本身外还需要额外的指针字段。对于大量小消息的情况，可能会导致空间浪费。
 * 3.性能问题: 当队列中包含大量消息时，入队和出队操作的时间复杂度为O(1)，但如果队列很长，查找操作可能会变得很慢，因为查找操作需要遍历链表。对于需要频繁查找消息的场景，性能可能会受到影响。
 * 4.缺乏扩展性: 上述实现只是一个简单的消息队列，缺乏一些高级功能，如消息优先级、消息持久化、队列持久化等。
 * 因此，在实际生产环境中，可能需要根据具体的需求和性能要求选择更合适的消息队列实现，如基于数组的循环队列、基于链表的双端队列、基于堆的优先级队列，或者使用成熟的消息队列中间件（如RabbitMQ、Kafka、ActiveMQ等）来满足复杂的消息处理需求。
 * @since 2024-05-22 14:34
 */
class ListNode {
    String message;
    ListNode next;

    public ListNode(String message) {
        this.message = message;
        this.next = null;
    }
}

public class MessageQueue {
    private ListNode head;
    private ListNode tail;
    private int size;

    public MessageQueue() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    // 入队操作，将新消息添加到队列尾部
    public void enqueue(String message) {
        ListNode newNode = new ListNode(message);
        if (isEmpty()) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        size++;
    }

    // 出队操作，从队列头部移除消息并返回
    public String dequeue() {
        if (isEmpty()) {
            return null;
        }
        String message = head.message;
        head = head.next;
        size--;
        if (isEmpty()) {
            tail = null;
        }
        return message;
    }

    // 获取队列大小
    public int size() {
        return size;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    public static void main(String[] args) {
        // 创建一个消息队列
        MessageQueue queue = new MessageQueue();

        // 测试入队和出队操作
        queue.enqueue("Message 1");
        queue.enqueue("Message 2");
        queue.enqueue("Message 3");

        // 测试队列大小
        System.out.println("Queue size: " + queue.size()); // Output: 3

        // 出队并打印出队的消息
        System.out.println(queue.dequeue()); // Output: Message 1
        System.out.println(queue.dequeue()); // Output: Message 2

        // 测试队列大小
        System.out.println("Queue size: " + queue.size()); // Output: 1

        // 再次入队和出队
        queue.enqueue("Message 4");
        System.out.println(queue.dequeue()); // Output: Message 3
        System.out.println(queue.dequeue()); // Output: Message 4

        // 测试队列是否为空
        System.out.println("Is queue empty? " + queue.isEmpty()); // Output: true
    }
}

